import java.util.*;

public class BinaryTree implements IBinaryTree{
    static class TreeNode {
        public char val;
        public TreeNode left;
        public TreeNode right;

        public TreeNode(char val) {
            this.val = val;
        }
    }
    public TreeNode createTree() {
        TreeNode A = new TreeNode('A');
        TreeNode B = new TreeNode('B');
        TreeNode C = new TreeNode('C');
        TreeNode D = new TreeNode('D');
        TreeNode E = new TreeNode('E');
        TreeNode F = new TreeNode('F');
        TreeNode G = new TreeNode('G');
        TreeNode H = new TreeNode('H');
        A.left = B;
        A.right = C;
        B.left = D;
        B.right = E;
        C.left = F;
        C.right = G;
        E.right = H;
        return A;
    }
    // 前序遍历
    public void preOrder(TreeNode root){
        if(root==null) {
            return ;
        }
        System.out.print(root.val+" ");
        preOrder(root.left);
        preOrder(root.right);

    }

    //非递归
    public void preOrderNor(TreeNode root) {
        if(root==null) {
            return;
        }
        Stack<TreeNode> stack=new Stack<>();
        TreeNode cur=root;
        while(cur!=null||!stack.isEmpty()) {
            while (cur != null) {
                stack.push(cur);
                System.out.print(cur.val + " ");
                cur = cur.left;
            }
            TreeNode top = stack.pop();
            cur = top.right;
        }
    }


    // 中序遍历
    public void inOrder(TreeNode root){
        if(root==null) {
            return;
        }
        inOrder(root.left);
        System.out.print(root.val+" ");
        inOrder(root.right);

    }

    //非递归
    public  void inOrderNor(TreeNode root) {
        if(root==null) {
            return;
        }
        Stack<TreeNode> stack=new Stack<>();
        TreeNode cur=root;
        while ((cur!=null||!stack.isEmpty())) {
            while(cur!=null) {
                stack.push(cur);
                cur=cur.left;
            }
            TreeNode top=stack.pop();
            System.out.print(top.val+" ");
            cur=top.right;
        }
    }

    // 后序遍历
    public void postOrder(TreeNode root) {
        if(root==null) {
            return;
        }
        postOrder(root.left);
        postOrder(root.right);
        System.out.print(root.val+" ");
    }
    //非递归
    public void postOrderNor(TreeNode root) {
        if(root==null) {
            return;
        }
        Stack<TreeNode> stack=new Stack<>();
        TreeNode cur=root;
        TreeNode prev=null;
        while (cur!=null||!stack.isEmpty()) {
            while (cur != null) {
                stack.push(cur);
                cur = cur.left;
            }
            TreeNode top = stack.peek();
            if (top.right==null||top.right==prev) {
                System.out.print(top.val+" ");
                stack.pop();
                prev=top; //记录下当前被打印的节点
            }else {
                //右边已经被打印了
                cur=top.right;
            }
        }
    }


   /* List<Integer> list=new LinkedList();
    public List<Integer> preorderTraversal(TreeNode root) {
        if(root==null) {
            return list;
        }
        list.add(root.val);
        preorderTraversal(root.left);
        preorderTraversal(root.right);
        return list;
    }*/


    //运用返回值
   /*public List<Integer> preorderTraversal(TreeNode root) {
       List<Integer> list=new ArrayList<>();
       if (root == null) {
           return list;
       }
       list.add(root.val);
       List<Integer> leftTree=preorderTraversal(root.left);
       list.addAll(leftTree);
       List<Integer> rightTree=preorderTraversal(root.right);
       list.addAll(rightTree);
       return list;
   }*/

    public int nodeSize=0;
    public int size(TreeNode root) {
        if(root==null) {
            return 0;
        }
       nodeSize++;
       size(root.left);
       size(root.right);
       return nodeSize;
    }

    //子问题解决size()
    public int size2(TreeNode root) {
        if(root==null) {
            return 0;
        }
        //左子树的大小+右子树的大小+根节点自己本身（1）
        return size2(root.left)+size2(root.right)+1;
    }

    public int leafSize=0;
    public int getLeafNodeCount(TreeNode root){
        if(root==null) {
            return 0;
        }
        if(root.right==null&&root.left==null) {
            leafSize++;
        }
        getLeafNodeCount(root.left);
        getLeafNodeCount(root.right);
        return leafSize;
    }
    public int getLeafNodeCount2(TreeNode root) {
        if(root==null) {
            return 0;
        }
        if(root.left==null&&root.right==null) {
            return 1;
        }
        return getLeafNodeCount2(root.left)
                +getLeafNodeCount2(root.right);
    }

    public int getKlevelNodeCount(TreeNode root,int k) {
        if(root==null) {
            return 0;
        }
        if(k==1) {
            return 1;
        }
            return getKlevelNodeCount(root.left, k - 1)
                    + getKlevelNodeCount(root.right, k - 1);
    }

    public int getTreeHeight(TreeNode root) {
        if(root==null) {
            return 0;
        }
        int leftHeight=getTreeHeight(root.left);
        int rightHeight=getTreeHeight(root.right);
        return leftHeight>rightHeight?leftHeight+1:rightHeight+1;
    }

    public TreeNode find(TreeNode root,char val) {
        if(root==null) {
            return null;
        }
        if(root.val==val) {
            return root;
        }
        TreeNode ret1=find(root.left,val);
        if(ret1!=null) {
            return ret1;
        }
        TreeNode ret2=find(root.right,val);
        if(ret2!=null) {
            return ret2;
        }
        return null;
    }

    public boolean isSameTree(TreeNode p, TreeNode q) {
        if(p==null&&q==null) {
            return true;
        }
        if(p==null&&q!=null) {
            return false;
        }
        if (p!=null&&q==null) {
            return false;
        }
        if(p.val!=q.val) {
            return false;
        }

        return  isSameTree(p.left,q.left)&&
                isSameTree(p.right,q.right);
    }
    public boolean isSubtree(TreeNode root, TreeNode subRoot) {
        if(isSameTree(root,subRoot)) {
            return true;
        }
        if(isSubtree(root.left,subRoot)){
            return true;
        }
        if (isSubtree(root.left,subRoot)) {
            return true;
        }
        return false;
    }

    //给你一棵二叉树的根节点 root ，翻转这棵二叉树，并返回其根节点。
    public TreeNode invertTree(TreeNode root) {
        if(root==null) {
            return null;
        }
        TreeNode tmp=root.right;
        root.right=root.left;
        root.left=tmp;
        invertTree(root.left);
        invertTree(root.right);
        return root;
    }
    /* public boolean isBalanced(TreeNode root) {
        if(root==null) {
            return true;
        }
        int leafHeight=maxDepth(root.left);
        int rightHeight=maxDepth(root.right);
        return Math.abs(leafHeight-rightHeight)<=1
                &&isBalanced(root.right)&&isBalanced(root.left);
    }
    public int maxDepth(TreeNode root) {
        if(root==null) {
            return 0;
        }
        int leafHeight=maxDepth(root.left);
        int rightHeight=maxDepth(root.right);
        return leafHeight>rightHeight?leafHeight+1:rightHeight+1;
    }*/
    public boolean isBalanced(TreeNode root) {
        if(root==null) {
            return true;
        }
        if(maxDepth(root)==-1) {
            return false;
        }
        return true;
    }
    public int maxDepth(TreeNode root) {
        if(root==null) {
            return 0;
        }
        int leafHeight=maxDepth(root.left);
        int rightHeight=maxDepth(root.right);
        if(leafHeight<0||rightHeight<0) {
            return -1;
        }
        if(leafHeight>=0&&rightHeight>=0&&Math.abs(leafHeight-rightHeight)<=1) {
            return Math.max(rightHeight,leafHeight)+1;
        }else{
            return -1;
        }
    }

    //对称二叉树
    public boolean isSymmetric(TreeNode root) {
        if(root==null) {
            return true;
        }
        return isSymmetricChild(root.left,root.right);
    }
    public boolean isSymmetricChild(TreeNode leftTree,TreeNode rightTree) {
        if(leftTree==null&&rightTree==null) {
            return true;
        }
        if(leftTree!=null&&rightTree==null) {
            return false;
        }
        if(leftTree==null&&rightTree!=null) {
            return false;
        }
        if(leftTree.val!=rightTree.val) {
            return false;
        }
        return isSymmetricChild(leftTree.left,rightTree.right)
                &&isSymmetricChild(leftTree.right,rightTree.left);
    }

    /*
https://www.nowcoder.com/practice/4b91205483694f449f94c179883c1fef?tpId=60&&tqId=29483&rp=1&ru=/activity/oj&qru=/ta/tsing-kaoyan/question-ranking
    class TreeNode {

    public char val;

    public TreeNode left;
    public TreeNode right;

    public TreeNode(char val) {
        this.val = val;
    }
}


// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {

    public static int i = 0;
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNextLine()) { // 注意 while 处理多个 case
            String str = in.nextLine();

            TreeNode root = createTree(str);

            inorder(root);
        }
    }

    public static TreeNode createTree(String str) {
        //1. 遍历字符串str
        // for(int i = 0;i < str.length();i++) {
        //     char ch = str.charAt(i);
        // }
        TreeNode root = null;
        if(str.charAt(i) != '#') {
            //2. 根据前序遍历创建二叉树
            root = new TreeNode(str.charAt(i));
            i++;
            root.left = createTree(str);
            root.right = createTree(str);
        }else {
            i++;
        }
        //3.返回根节点
        return root;
    }

    public static void inorder(TreeNode root) {
        if(root == null) {
            return ;
        }
        inorder(root.left);

        System.out.print(root.val+" ");

        inorder(root.right);

    }

}
     */


    //层序遍历
    public void levelOrder(TreeNode root) {
        if(root==null) {
            return;
        }
        Queue<TreeNode> queue=new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()) {
            TreeNode cur = queue.poll();
            System.out.print(cur.val + " ");
            if (cur.left != null) {
                queue.offer(cur.left);
            }
            if (cur.right != null) {
                queue.offer(cur.right);
            }
        }
    }

   /* //层序遍历2
    //https://leetcode.cn/problems/binary-tree-level-order-traversal/
    public List<List<Integer>> levelOrderBottom(TreeNode root) {
        List<List<Integer>> ret=new ArrayList<>();
        if(root==null) {
            return ret;
        }
        Queue<TreeNode> queue=new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()) {
            int size = queue.size();
            List<Integer> tmp=new ArrayList<>();
            while ((size != 0)) {
                TreeNode cur = queue.poll();
                tmp.add(cur.val);
                size--;
                System.out.print(cur.val + " ");
                if (cur.left != null) {
                    queue.offer(cur.left);
                }
                if (cur.right != null) {
                    queue.offer(cur.right);
                }
            }
            ret.add(tmp);
        }
        return ret;
    }

*/

    //是否是完全二叉树
    public boolean isCompleteTree(TreeNode root) {
        Queue<TreeNode> queue=new LinkedList<>();
        if(root==null) {
            return true;
        }
        queue.offer(root);
        while (!queue.isEmpty()) {
            TreeNode cur=queue.poll();
            if(cur!=null) {
            queue.offer(cur.left);
            queue.offer(cur.right);
            }else {
                break;//结束循环
            }
        }
        //需要判断队列是不是全为空
        while(!queue.isEmpty()){
            if(queue.poll()!=null) {
                return false;
            }
        }
        return true;
    }

    //最近公共祖先
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root==null) {
            return root;
        }
        if(root==q||root==p) {
            return root;
        }
        TreeNode leftNode=lowestCommonAncestor(root.left,p,q);
        TreeNode rightNode=lowestCommonAncestor(root.right,p,q);
        if(leftNode!=null&&rightNode!=null) {
            return root;
        }
        if(leftNode!=null) {
            return leftNode;
        }else {
            return rightNode;
        }
    }

    //交点法求公共祖先
    public TreeNode lowestCommonAncestor2(TreeNode root, TreeNode p, TreeNode q) {
        if(root==null) {
            return null;
        }
        Stack<TreeNode> stackP=new Stack<>();
        Stack<TreeNode> stackQ=new Stack<>();
        getpath(root,p,stackP);
        getpath(root,q,stackQ);
        int sizeP=stackP.size();
        int sizeQ=stackQ.size();
        if(sizeP>sizeQ) {
            int size=sizeP-sizeQ;
            while (size!=0) {
                stackP.pop();
                size--;
            }
            }else{
            int size=sizeQ-sizeP;
            while (size!=0) {
                stackQ.pop();
                size--;
            }
        }
        while(!stackQ.isEmpty()&&!stackP.isEmpty()) {
            if(stackP.peek()==stackQ.peek()) {
                return stackP.peek();
            }else {
                stackP.pop();
                stackQ.pop();
            }
        }
        return null;

    }

    public boolean getpath(TreeNode root, TreeNode node, Stack<TreeNode> stack) {
        if(root==null||node==null) {
            return false;
        }
        stack.push(root);
        if(root==node) {
            return true;
        }
        boolean flg=getpath(root.left,node,stack);
        if(flg==true) {
            return true;
        }
        boolean flg2=getpath(root.right,node,stack);
        if(flg2==true) {
            return true;
        }
        stack.pop();
        return false;
    }

    //前序遍历中序遍历创建二叉树
   /* class Solution {
        public int preIndex=0;
        public TreeNode buildTree(int[] preorder, int[] inorder) {

            return buildTreeChilde(preorder,inorder,0,inorder.length-1);

        }

        private TreeNode buildTreeChilde(int[] preorder,int[] inorder,int inbegin,int inend) {
            if(inbegin>inend) {
                return null;
            }


            TreeNode root = new TreeNode(preorder[preIndex]);
            int rootIndex=fineIndex(inorder,inbegin,inend,preorder[preIndex]);
            if(rootIndex==-1) {
                return null;
            }
            preIndex++;
            root.left=buildTreeChilde(preorder,inorder,inbegin,rootIndex-1);
            root.right=buildTreeChilde(preorder,inorder,rootIndex+1,inend);

            return root;
        }

        private int fineIndex(int[] inorder,int inbegin,int inend,int key) {
            for(int i=inbegin;i<=inend;i++) {
                if(inorder[i]==key) {
                    return i;
                }

            }
            return -1;
        }


    }
    */

    //中后序遍历创建二叉树
    /* class Solution {
    public int postIndex;

    public TreeNode buildTree(int[] inorder, int[] postorder) {
        postIndex=postorder.length-1;

        return buildTreeChilde(postorder,inorder,0,inorder.length-1);

    }

    private TreeNode buildTreeChilde(int[] postorder,int[] inorder,int inbegin,int inend) {
        if(inbegin>inend) {
            return null;
        }
        TreeNode root = new TreeNode(postorder[postIndex]);
        int rootIndex=findIndex(inorder,inbegin,inend,postorder[postIndex]);
        if(rootIndex==-1) {
            return null;
        }
        postIndex--;

        root.right=buildTreeChilde(postorder,inorder,rootIndex+1,inend);
        root.left=buildTreeChilde(postorder,inorder,inbegin,rootIndex-1);

        return root;
    }

    private int findIndex(int[] inorder,int inbegin,int inend,int key) {
        for(int i=inbegin;i<=inend;i++) {
            if(inorder[i]==key) {
                return i;
            }

        }
        return -1;
    }


}
*/


}

